package sort;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
//        int[] nums = new int[]{2, 34, 56, 43, 99, 6, 7, 4, 3, 5, 6, 7, 65, 3, 2};
//        insertionSort(nums);
//        System.out.println(Arrays.toString(nums));

        int testTime = 5000;
        int maxSize = 10000;
        int maxValue = 10000;
        boolean succeed = true;

        for(int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr = copyArray(arr1);
            insertionSort(arr1);
            Arrays.sort(arr);
            if (!isEqual(arr, arr1)){
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "nice" : "fuck");
    }

    private static boolean isEqual(int[] arr, int[] arr1) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != arr1[i]) {
                return false;
            }
        }
        return true;
    }

    private static int[] copyArray(int[] arr1) {
        int[] arr = new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr[i] = arr1[i];
        }
        return arr;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        // Math.random();   --> [0, 1) 的所有小数，等概率返回一个
        // Math.random() * N    -->     [0, N) 的所有小数
        // (int) (Math.random() * N)    -->     [0, N) --> [0, N-1] 整数
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());//[-(maxValue-1), maxValue]
        }
        return arr;
    }

    public static void insertionSort(int[] nums) {
        if (nums.length < 2 || nums == null) {
            return;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0 && nums[j] > nums[j+1]; j--) {
                swap(nums, j, j + 1);
            }
        }
/*
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] > nums[j - 1]) {
                    break;
                } else {
                    swap(nums, j, j - 1);
                }
            }
        }
*/
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
